#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/9/27 9:16
# @Author  : Yuyun
# @File    : leetcode_5_最长回文字串.py
# @IDE     : PyCharm
"""
给你一个字符串 s，找到 s 中最长的 回文子串

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"

提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
"""

class Solution:
    """
    dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
    当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

    情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
    情况二：下标i 与 j相差为1，例如aa，也是回文子串
    情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，
    那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

    dp[i][j]初始化为false。
    """
    def judge_sub_palindrome_dp(self, s):
        sub_start = 0
        sub_end = 0
        sub_len = 0
        length = len(s)

        dp = [[False] * length for _ in range(length)]
        for i in range(length - 1, -1, -1):
            for j in range(i, length):
                if s[i] == s[j]:
                    if j - i <= 1:
                        dp[i][j] = True
                    elif dp[i + 1][j - 1]:
                        dp[i][j] = True
                if dp[i][j] and j - i + 1 > sub_len:
                    sub_len = j - i + 1
                    sub_start = i
                    sub_end = j
        return s[sub_start:sub_end + 1], sub_len
    """
    双指针法：从某一个字符、或者某两个字符展开，向左右两边判断回文串
    """

    def extend(self, s, left, right, length):  # 输出每个回文字符串、和对应长度
        sub_len = 0
        while left >= 0 and right < length and s[left] == s[right]:
            sub_len = right - left + 1  # 此时符合回文条件的子字符串长度
            left -= 1
            right += 1
        return s[left + 1: right], sub_len  # left - 1和right + 1操作后，才跳出循环，故截取字符串时，需要[left+1:right]
    def judge_sub_palindrome_index(self,s):
        length = len(s)
        max_sub_len = 0
        max_sub_str = ''
        for i in range(length):
            sub_1, len_1 = self.extend(s, i, i, length)  # 以i 单个字符扩展
            sub_2, len_2 = self.extend(s, i, i + 1, length)  # 以i , i+1两个字符扩展
            if len_2 > max_sub_len:
                max_sub_len = len_2
                max_sub_str = sub_2
            elif len_1 > max_sub_len:
                max_sub_len = len_1
                max_sub_str = sub_1
        return max_sub_str, max_sub_len

    # 方法③——python字符串直接将每个字串逆序对比
    def judge_sub_palindromic_str(slef, s):
        # 长度递减，for用于遍历字符串长度中的数字3,2,1,0；从大到小控制回文长度,所以返回的第一个回文必是最长回文子串
        for i in range(len(s), 0, -1):
            # 分别控制不同长度回文的位置
            for j in range(0, len(s) - i + 1):
                # 回文判断
                if s[j: j + i] == s[j: j + i][::-1]:
                    return s[j: j + i], i

    def judge_sub_palindromic_str_I(self, s):
        lenth = len(s)
        max_sub_length = 0
        max_sub_s = ''
        for i in range(lenth):
            for j in range(i + 1, lenth):
                slice_s = slice(i, j)
                sub_s = s[slice_s]
                sub_length = len(s[slice_s])
                # 循环判断字串是否为回文串
                if sub_s[:] == sub_s[::-1] and sub_length > max_sub_length:
                    max_sub_s = sub_s
                    max_sub_length = sub_length
        return max_sub_s, max_sub_length
if __name__ == '__main__':
    s = input()
    result_s, result_l = Solution().judge_sub_palindrome_dp(s)
    print(result_s)